package com.cb2.algorithm.leetcode;

/**
 * <a href='https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-postorder-traversal/'>根据前序和后序遍历构造二叉树(Construct Binary Tree from Preorder and Postorder Traversal)</a>
 * <p>给定两个整数数组，preorder 和 postorder ，其中 preorder 是一个具有 无重复 值的二叉树的前序遍历，postorder 是同一棵树的后序遍历，重构并返回二叉树。</p>
 * <p>如果存在多个答案，您可以返回其中 任何 一个。</p>
 * <p>
 * <b>示例：</b>
 * <pre>
 *  示例 1：
 *      输入：preorder = [1,2,4,5,3,6,7], postorder = [4,5,2,6,7,3,1]
 *      输出：[1,2,3,4,5,6,7]
 *
 * 示例 2:
 *      输入: preorder = [1], postorder = [1]
 *      输出: [1]
 * </pre>
 * </p>
 * <p>
 * <b>提示：</b>
 *     <ul>
 *         <li>1 <= preorder.length <= 30</li>
 *         <li>1 <= preorder[i] <= preorder.length</li>
 *         <li>preorder 中所有值都 不同</li>
 *         <li>postorder.length == preorder.length</li>
 *         <li>1 <= postorder[i] <= postorder.length</li>
 *         <li>postorder 中所有值都 不同</li>
 *         <li>保证 preorder 和 postorder 是同一棵二叉树的前序遍历和后序遍历</li>
 *     </ul>
 * </p>
 *
 * @author c2b
 * @see LC0105ConstructBinaryTreeFromPreorderAndInorderTraversal_M 从前序与中序遍历序列构造二叉树
 * @see LC0106ConstructBinaryTreeFromInorderAndPostorderTraversal_M 从中序与后序遍历序列构造二叉树
 * @see LC0889ConstructBinaryTreeFromPreorderAndPostorderTraversal_M 从前序与后序遍历序列构造二叉树
 * @since 2024/3/1 15:06
 */
public class LC0889ConstructBinaryTreeFromPreorderAndPostorderTraversal_M {
    static class Solution {
        public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
            // 题目限定了，节点的值为[1-30]共31个元素；这里可以使用数组代替
            //Map<Integer, Integer> value2IndexInPostorderMap = new HashMap<>();
            int[] value2IndexInPostorderMap = new int[31];
            for (int i = 0; i < postorder.length; i++) {
                value2IndexInPostorderMap[postorder[i]] = i;
            }
            return doBuildTree(preorder,
                    value2IndexInPostorderMap,
                    0,
                    preorder.length - 1,
                    0,
                    postorder.length - 1
            );
        }

        /**
         * <p>前序遍历：根->左->右</p>
         * <p>后序遍历：左->右->根</p>
         * <p>
         * 思路：前序遍历中：第一个元素为根节点，根节点的下一个元素作为左子树的根节点。
         * 在后续遍历中找到左子树的根节点的位置，左侧(含自身)作为左子树；右侧作为右子树(需要去除根节点的1个节点)
         * </p>
         */
        private TreeNode doBuildTree(int[] preorder,
                                     //Map<Integer, Integer> value2IndexInPostorderMap,
                                     int[]value2IndexInPostorderMap,
                                     int pre_start, int pre_end, int post_start, int post_end) {

            if (pre_start > pre_end) {
                return null;
            }
            TreeNode root = new TreeNode(preorder[pre_start]);
            if (pre_start == pre_end) {
                return root;
            }
            // 替换成Map
            //int leftTreeRootIndexInPostorder = value2IndexInPostorderMap.get(preorder[pre_start + 1]);
            int leftTreeRootIndexInPostorder = value2IndexInPostorderMap[preorder[pre_start + 1]];
            // leftTreeNodeCount：左子树节点的数量
            int leftTreeNodeCount = leftTreeRootIndexInPostorder - post_start + 1;
            root.left = doBuildTree(preorder,
                    value2IndexInPostorderMap,
                    pre_start + 1,
                    // pre_start + 1 ：前序遍历中左子树的起始位置；
                    // leftTreeRootIndexInPostorder - post_start：左子树中节点数量
                    pre_start + leftTreeNodeCount,
                    post_start,
                    leftTreeRootIndexInPostorder
            );
            root.right = doBuildTree(
                    preorder,
                    value2IndexInPostorderMap,
                    //pre_start + 1 + 1 + leftTreeRootIndexInPostorder - post_start,
                    pre_start + 1 + leftTreeNodeCount,
                    pre_end,
                    // leftTreeRootIndexInPostorder + 1：左子树根节点的后一个节点
                    leftTreeRootIndexInPostorder + 1,
                    post_end - 1
            );
            return root;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        Printer.printTreeNode(solution.constructFromPrePost(new int[]{1, 2, 4, 5, 3, 6, 7}, new int[]{4, 5, 2, 6, 7, 3, 1}));
        Printer.printTreeNode(solution.constructFromPrePost(new int[]{1}, new int[]{1}));
    }
}